package class08_前缀树不基于比较的排序排序的稳定性.test;

import class33_与哈希函数有关的节点.Hash;

import java.util.HashMap;

public class Code02_TrieTree {
    public static class Node{
        private int pass;
        private int end;
        private Node[] nexts;

        public Node(){
            this.pass = 0;
            this.end = 0;
            nexts = new Node[26];
        }
        public void insert(String str){
            char[] chars = str.toCharArray();
            Node cur = this;
            cur.pass++;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(cur.nexts[index] == null){
                    cur.nexts[index] = new Node();
                }
                cur.nexts[index].pass++;
                cur = cur.nexts[index];
            }
            cur.end++;
        }

        public void remove(String str){
            int sreach = search(str);
            if(sreach > 0){
                char[] chars = str.toCharArray();
                Node cur = this;
                for (int i = 0; i < chars.length; i++) {
                    int index = chars[i] - 'a';
                    if(cur.nexts[index].pass == 1){
                        cur.nexts[index] = null;//防止内存泄漏
                        return;
                    }else {
                        cur.nexts[index].pass--;
                        cur = cur.nexts[index];
                    }
                }
                cur.end--;
            }
        }
        public int search(String str){
            char[] chars = str.toCharArray();
            Node cur = this;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(cur.nexts[index] == null){
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.end;
        }
        public int sreachPrefix(String str){
            char[] chars = str.toCharArray();
            Node cur = this;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(cur.nexts[index] == null){
                    return 0;
                }
                cur = cur.nexts[index];
            }
            return cur.pass;
        }
    }

    public static class Node2{
        private int pass;
        private int end;
        private HashMap<Integer, Node2> nexts;
        public Node2(){
            this.pass = 0;
            this.end = 0;
            this.nexts = new HashMap<>();
        }

        public void insert(String str){
            char[] chars = str.toCharArray();
            Node2 cur = this;
            cur.pass++;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(!cur.nexts.containsKey(index)){
                    cur.nexts.put(index, new Node2());
                }
                cur = cur.nexts.get(index);
                cur.pass++;
            }
            cur.end++;
        }
        public void remove(String str){
            int search = search(str);
            if(search > 0){
                char[] chars = str.toCharArray();
                Node2 cur = this;
                cur.pass--;
                for (int i = 0; i < chars.length; i++) {
                    int index = chars[i] - 'a';
                    if(cur.nexts.get(index).pass == 1){
                        cur.nexts.remove(index);
                        return;
                    }else {
                        cur = cur.nexts.get(index);
                        cur.pass--;
                    }
                }
                cur.end--;
            }
        }
        public int search(String str){
            char[] chars = str.toCharArray();
            Node2 cur = this;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(!cur.nexts.containsKey(index)){
                    return 0;
                }
                cur = cur.nexts.get(index);
            }
            return cur.end;
        }
        public int searchPrefix(String str){
            char[] chars = str.toCharArray();
            Node2 cur = this;
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                if(!cur.nexts.containsKey(index)){
                    return 0;
                }
                cur = cur.nexts.get(index);
            }
            return cur.pass;
        }
    }

    public static class Right{
        private HashMap<String, Integer> box;
        public Right(){
            box = new HashMap<>();
        }
        public void insert(String str){
            if(box.containsKey(str)){
                box.put(str, box.get(str) + 1);
            }else {
                box.put(str, 1);
            }
        }
        public void remove(String str){
            if(box.containsKey(str)){
                if(box.get(str) == 1){
                    box.remove(str);
                }else {
                    box.put(str, box.get(str) - 1);
                }
            }
        }
        public int search(String str){
            if(box.containsKey(str)){
                return box.get(str);
            }
            return 0;
        }
        public int searchPrefix(String pre){
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }
    public static void main(String[] args) {
        System.out.println("begain!!!");
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 500000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            Node trie1 = new Node();
            Node2 trie2 = new Node2();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    trie2.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.remove(arr[j]);
                    trie2.remove(arr[j]);
                    right.remove(arr[j]);
                } else if (decide < 0.75) {
                    int ans1 = trie1.search(arr[j]);
                    int ans2 = trie2.search(arr[j]);
                    int ans3 = right.search(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                } else {
                    int ans1 = trie1.sreachPrefix(arr[j]);
                    int ans2 = trie2.searchPrefix(arr[j]);
                    int ans3 = right.searchPrefix(arr[j]);
                    if (ans1 != ans2 || ans2 != ans3) {
                        System.out.println("Oops!");
                    }
                }

            }
        }
        System.out.println("final!!!");
    }

    private static String[] generateRandomStringArray(int arrLen, int strLen) {
        String[] arr = new String[(int)(Math.random() * arrLen + 1)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = generateRandomString(strLen);
        }
        return arr;
    }

    private static String generateRandomString(int strLen) {
        char[] ans = new char[(int)(Math.random() * strLen + 1)];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (char)(97 + (int)(Math.random() * 6));
        }
        return String.valueOf(ans);
    }
}
